#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

namespace lh
{
    struct TreeNode {
        int val;
        struct TreeNode* left;
        struct TreeNode* right;
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    };

    class Solution {
    public:
        //前序遍历
        void PreOrder(vector<int>& res, TreeNode* root)
        {
            //空节点退出
            if (root == nullptr)
                return;
            //存入根节点
            res.push_back(root->val);
            //遍历左右
            PreOrder(res, root->left);
            PreOrder(res, root->right);
        }

        vector<int> preorderTraversal(TreeNode* root) {
            vector<int>res;
            PreOrder(res, root);
            return res;
        }

        //中序遍历
        void InOrder(vector<int>& res, TreeNode* root)
        {
            //空节点退出
            if (root == nullptr)
                return;
            //遍历左节点
            InOrder(res, root->left);
            //存入根节点
            res.push_back(root->val);
            //遍历右节点
            InOrder(res, root->right);
        }
        vector<int> inorderTraversal(TreeNode* root) {
            vector<int>res;
            InOrder(res, root);
            return res;
        }

        //后序遍历
        void PostOrder(vector<int>&res, TreeNode * root)
        {
            //空节点退出
            if (root == nullptr)
                return;
            //遍历左右
            PostOrder(res, root->left);
            PostOrder(res, root->right);
            //存入根节点
            res.push_back(root->val);
        }
        vector<int> postorderTraversal(TreeNode * root) {
            vector<int>res;
            PostOrder(res, root);
            return res;
        }

    };

    void test()
    {
        TreeNode* node1 = new TreeNode(1);
        TreeNode* node2 = new TreeNode(2);
        TreeNode* node3 = new TreeNode(3);
        TreeNode* node4 = new TreeNode(4);
        TreeNode* node5 = new TreeNode(5);

        node1->left = node2;    node1->right = node3;
        node3->left = node4;    node3->right = node5;
        vector<int>res;
        cout << "前序遍历:" << endl;
        res=Solution().preorderTraversal(node1);
        for (auto p: res)
        {
            cout << p << ' ';
        }
        cout << endl;
        cout << "中序遍历:" << endl;
        res = Solution().inorderTraversal(node1);
        for (auto p : res)
        {
            cout << p << ' ';
        }
        cout << endl;
        cout << "后序遍历:" << endl;
        res = Solution().postorderTraversal(node1);
        for (auto p : res)
        {
            cout << p << ' ';
        }
        cout << endl;

        delete node1;
        delete node2;
        delete node3;
        delete node4;
        delete node5;
    }
    //BM26 层序遍历
    //https://www.nowcoder.com/practice/04a5560e43e24e9db4595865dc9c63a3?tpId=295&tqId=644&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution2 {
    public:
        void traverse(TreeNode* root, vector<vector<int>>& res, int depth)
        {
            if (root == nullptr)
                return;
            //若小于则表明为新一层，先插入一行（代表新层）
            if (res.size() < depth)
            {
                res.push_back(vector<int>{});
            }
            res[depth - 1].push_back(root->val);//下标从0开始，所以depth-1
            traverse(root->left, res, depth + 1);
            traverse(root->right, res, depth + 1);
        }
        vector<vector<int> > levelOrder(TreeNode* root) {
            vector<vector<int>>res;
            if (root == nullptr)
                return res;
            traverse(root, res, 1);
            return res;
        }
    };

    //BM27 按之字形顺序打印二叉树
    //https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0?tpId=295&tqId=23454&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution3 {
    public:
        //层次遍历
        void traverse(TreeNode* root, vector<vector<int>>& res, int depth)
        {
            if (root == nullptr)
                return;
            if (res.size() < depth)
            {
                res.push_back(vector<int>{});
            }
            res[depth - 1].push_back(root->val);
            traverse(root->left, res, depth + 1);
            traverse(root->right, res, depth + 1);
        }
        vector<vector<int> > Print(TreeNode* pRoot) {
            vector<vector<int>>res;
            if (pRoot == nullptr)
                return res;
            traverse(pRoot, res, 1);
            //反转
            for (int i = 0; i < res.size(); i++)
            {
                if ((i % 2) == 1)
                {
                    reverse(res[i].begin(), res[i].end());
                }
            }
            return res;
        }

    };
    void test2()
    {
        TreeNode* node1 = new TreeNode(1);
        TreeNode* node2 = new TreeNode(2);
        TreeNode* node3 = new TreeNode(3);
        TreeNode* node4 = new TreeNode(4);
        TreeNode* node5 = new TreeNode(5);

        node1->left = node2;    node1->right = node3;
        node3->left = node4;    node3->right = node5;
        vector<vector<int>>res;
        cout << "层序遍历:" << endl;
        res = Solution2().levelOrder(node1);
        for (int i = 0; i < res.size(); i++)
        {
            for (int j = 0; j < res[i].size(); j++)
            {
                cout << res[i][j] << ' ';
            }
        }
        cout << endl;
        cout << "之字形层序遍历:" << endl;
        res = Solution3().Print(node1);
        for (int i = 0; i < res.size(); i++)
        {
            for (int j = 0; j < res[i].size(); j++)
            {
                cout << res[i][j] << ' ';
            }
        }
        cout << endl;
        delete node1;
        delete node2;
        delete node3;
        delete node4;
        delete node5;
    }
}

int main()
{
    lh::test();
    lh::test2();
    return 0;
}